import java.util.ArrayList;
import java.util.List;

public class GenerateTrees {

    public List<TreeNode> generateTrees(int n) {
        return process(0, n);
    }

    public List<TreeNode> process(int start, int end) {
        List<TreeNode> list = new ArrayList<>();
        if (start > end) {
            list.add(null);
        } else if (start == end) {
            list.add(new TreeNode(start));
        } else {
            for (int i = start; i <= end; i++) {
                List<TreeNode> list1 = process(start, i - 1);
                List<TreeNode> list2 = process(i + 1, end);
                for (int j = 0; j < list1.size(); j++) {
                    for (int k = 0; k < list2.size(); k++) {
                        TreeNode head = new TreeNode(i);
                        head.left = list1.get(j);
                        head.right = list2.get(k);
                        list.add(head);
                    }
                }
            }
        }
        return list;
    }
}
